//给你一个产品数组 products 和一个字符串 searchWord ，products 数组中每个产品都是一个字符串。 
//
// 请你设计一个推荐系统，在依次输入单词 searchWord 的每一个字母后，推荐 products 数组中前缀与 searchWord 相同的最多三个产品
//。如果前缀相同的可推荐产品超过三个，请按字典序返回最小的三个。 
//
// 请你以二维列表的形式，返回在输入 searchWord 每个字母后相应的推荐产品的列表。 
//
// 
//
// 示例 1： 
//
// 输入：products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord 
//= "mouse"
//输出：[
//["mobile","moneypot","monitor"],
//["mobile","moneypot","monitor"],
//["mouse","mousepad"],
//["mouse","mousepad"],
//["mouse","mousepad"]
//]
//解释：按字典序排序后的产品列表是 ["mobile","moneypot","monitor","mouse","mousepad"]
//输入 m 和 mo，由于所有产品的前缀都相同，所以系统返回字典序最小的三个产品 ["mobile","moneypot","monitor"]
//输入 mou， mous 和 mouse 后系统都返回 ["mouse","mousepad"]
// 
//
// 示例 2： 
//
// 输入：products = ["havana"], searchWord = "havana"
//输出：[["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]
// 
//
// 示例 3： 
//
// 输入：products = ["bags","baggage","banner","box","cloths"], searchWord = 
//"bags"
//输出：[["baggage","bags","banner"],["baggage","bags","banner"],["baggage","bags"]
//,["bags"]]
// 
//
// 示例 4： 
//
// 输入：products = ["havana"], searchWord = "tatiana"
//输出：[[],[],[],[],[],[],[]]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= products.length <= 1000 
// 1 <= Σ products[i].length <= 2 * 10^4 
// products[i] 中所有的字符都是小写英文字母。 
// 1 <= searchWord.length <= 1000 
// searchWord 中所有字符都是小写英文字母。 
// 
//
// Related Topics 字典树 数组 字符串 二分查找 排序 堆（优先队列） 👍 164 👎 0


package LeetCode.editor.cn;

import java.util.*;

/**
 * @author ldltd
 * @date 2023-10-08 11:40:50
 * @description 1268.搜索推荐系统
 */
public class SearchSuggestionsSystem {
	public static void main(String[] args) {
		//测试代码
		Solution solution = new SearchSuggestionsSystem().new Solution();

	}

	//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
	class Solution {
		//排序 + 字典树 + 哈希表
		int[][] trie = new int[20010][26];
		int idx = 0;
		//key为字典树的位置，value为经过该节点的最大最小下标
		Map<Integer, Integer> min = new HashMap<>(), max = new HashMap<>();

		// num为products排序后的下标
		//如果首次访问即trie[p][u]==0.加入min，最后一次访问加入max
		void add(String s, int num) {
			int p = 0;
			for (int i = 0; i < s.length(); i++) {
				int u = s.charAt(i) - 'a';
				if (trie[p][u] == 0) {
					trie[p][u] = ++idx;
					min.put(trie[p][u], num);
				}
				max.put(trie[p][u], num);
				p = trie[p][u];
			}
		}

		//查询该子串最后字符在字典树中的节点值
		int[] query(String s) {
			int a = -1, b = -1, p = 0;
			for (int i = 0; i < s.length(); i++) {
				int u = s.charAt(i) - 'a';
				if (trie[p][u] == 0) return new int[]{-1, -1};
				a = min.get(trie[p][u]);
				b = max.get(trie[p][u]);
				p = trie[p][u];
			}
			return new int[]{a, b};
		}

		public List<List<String>> suggestedProducts(String[] products, String searchWord) {
			Arrays.sort(products);
			List<List<String>> res = new ArrayList<>();
			//先把products加入字典树
			for (int i = 0; i < products.length; i++) {
				add(products[i], i);
			}
			//依次递增字符搜索
			for (int i = 0; i < searchWord.length(); i++) {
				List<String> list = new ArrayList<>();
				int[] info = query(searchWord.substring(0, i + 1));
				int l = info[0], r = info[1];
				//只添加最多三个
				for (int j = l; j <= Math.min(l + 2, r) && l != -1; j++) {
					list.add(products[j]);
				}
				res.add(list);
			}
			return res;
		}

		//排序+二分
		/*对每个w子串，先找到满足要求的字典序最小的，再往后逐个检查*/
		public List<List<String>> suggestedProducts1(String[] products, String searchWord) {
			Arrays.sort(products);
			int length = products.length;
			List<List<String>> res = new ArrayList<>();
			for (int i = 0; i < searchWord.length(); i++) {
				String cur = searchWord.substring(0, i + 1);
				int l = 0, r = length - 1;
				while (l < r) {
					int mid = l + r >> 1;
					if (products[mid].compareTo(cur) >= 0) r = mid;
					else l = mid + 1;
				}
				List<String> list = new ArrayList<>();
				if (products[r].compareTo(cur) >= 0) {
					for (int j = r; j <= Math.min(length - 1, r + 2); j++) {
						if (products[j].length() > cur.length()) break;
						if (!products[j].substring(0, i + 1).equals(cur)) break;
						list.add(products[j]);
					}
				}
				res.add(list);
			}
			return res;
		}
	}
//leetcode submit region end(Prohibit modification and deletion)


}
